翻訳と辞書 |
Director string : ウィキペディア英語版 | Director string In mathematics, in the area of lambda calculus and computation, directors or director strings are a mechanism for keeping track of the free variables in a term. Loosely speaking, they can be understood as a kind of memoization for free variables; that is, as an optimization technique for rapidly locating the free variables in a term algebra or in a lambda expression. Director strings were introduced by Kennaway and Sleep in 1982 and further developed by Sinot, Fernández and Mackie 〔F.-R. Sinot, M. Fernández and I. Mackie. Efficient Reductions with Director Strings. In ''Proc. Rewriting Techniques and Applications''. Springer LNCS vol 2706, 2003〕 as a mechanism for understanding and controlling the computational complexity cost of beta reduction. ==Motivation== In beta reduction, one defines the value of the expression on the left to be that on the right: : or (Replace all ''x'' in ''E''(body) by ''y'') While this is a conceptually simple operation, the computational complexity of the step can be non-trivial: a naive algorithm would scan the expression ''E'' for all occurrences of the free variable ''x''. Such an algorithm is clearly ''O''(''n'') in the length of the expression ''E''. Thus, one is motivated to somehow track the occurrences of the free variables in the expression. One may attempt to track the position of ''every'' free variable, wherever it may occur in the expression, but this can clearly become very costly in terms of storage; furthermore, it provides a level of detail that is not really needed. Director strings suggest that the correct model is to track free variables in a hierarchical fashion, by tracking their use in component terms.
抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「Director string」の詳細全文を読む
スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|